home *** CD-ROM | disk | FTP | other *** search
/ Aminet 24 / Aminet 24 (1998)(GTI - Schatztruhe)[!][Apr 1998].iso / Aminet / dev / c / vbcc.lha / vbcc / cse.c < prev    next >
C/C++ Source or Header  |  1997-12-30  |  13KB  |  377 lines
  1. /*  $VER: vbcc (cse.c) V0.4     */
  2. /*  verfuegbare Ausdruecke und common subexpression elimination */
  3.  
  4. #include "opt.h"
  5.  
  6. static char FILE_[]=__FILE__;
  7.  
  8. /*  fuer verfuegbare Ausdruecke */
  9. struct IC **elist;
  10. unsigned int ecount;
  11. size_t esize;
  12. unsigned char *ae_globals,*ae_statics,*ae_address,*ae_drefs;
  13. unsigned char **ae_kills;
  14.  
  15. void available_expressions(struct flowgraph *fg)
  16. /*  berechnet die verfuegbaren Ausdruecke fuer jeden Block      */
  17. {
  18.     struct flowgraph *g;struct IC *p;unsigned char *tmp;
  19.     int changed,pass,i,j;
  20.     /*  ae_gen und ae_kill fuer jeden Block berechnen   */
  21.     if(DEBUG&1024) printf("analysing available expressions\n");
  22.     tmp=mymalloc(esize);
  23.     g=fg;
  24.     while(g){
  25.         g->ae_in=mymalloc(esize);
  26.         memset(g->ae_in,0,esize);
  27.         g->ae_out=mymalloc(esize);
  28.         memset(g->ae_out,0,esize);
  29.         g->ae_gen=mymalloc(esize);
  30.         memset(g->ae_gen,0,esize);
  31.         g->ae_kill=mymalloc(esize);
  32.         memset(g->ae_kill,0,esize);
  33.         p=g->end;
  34.         while(p){
  35.             memset(tmp,0,esize);
  36.             for(j=0;j<p->change_cnt;j++){
  37.                 i=p->change_list[j].v->index;
  38.                 if(p->change_list[j].flags&DREFOBJ) i+=vcount-rcount;
  39.                 if(i>=vcount) continue;
  40.                 bvunite(tmp,ae_kills[i],esize);
  41.             }
  42.             bvdiff(tmp,g->ae_gen,esize);
  43.             bvunite(g->ae_kill,tmp,esize);
  44.             i=p->expindex;
  45.             if(i>=0&&!BTST(g->ae_kill,i)) BSET(g->ae_gen,i);
  46.  
  47.             if(p==g->start) break;
  48.             p=p->prev;
  49.         }
  50.         if(g==fg){
  51.             memset(g->ae_in,0,esize);
  52.             memcpy(g->ae_out,g->ae_gen,esize);
  53.         }else{
  54.             memset(g->ae_out,UCHAR_MAX,esize);
  55.             bvdiff(g->ae_out,g->ae_kill,esize);
  56.         }
  57.         g=g->normalout;
  58.     }
  59.  
  60.     /*  ae_in und ae_out fuer jeden Block berechnen */
  61.     /*  out(b)=U-gen(B) vorinitialisiert und        */
  62.     /*  in(B0)=0, out(B0)=gen(B0)                   */
  63.     if(DEBUG&1024) {printf("pass:");pass=0;}
  64.     do{
  65.         if(DEBUG&1024) {printf(" %d",++pass);fflush(stdout);}
  66.         changed=0;
  67.         g=fg->normalout;    /*  in B0 aendert sich nichts   */
  68.         while(g){
  69.             struct flowlist *lp;
  70.             /*  in(B)=Schnitt out(P) mit P Vorgaenger von B */
  71.             lp=g->in;
  72.             i=0;    /*  Flag fuer ersten Vorgaenger */
  73.             while(lp){
  74.                 if(!lp->graph) ierror(0);
  75.                 if(lp->graph->branchout==g||!lp->graph->end||lp->graph->end->code!=BRA){
  76.                     if(i){
  77.                         bvintersect(g->ae_in,lp->graph->ae_out,esize);
  78.                     }else{
  79.                         memcpy(g->ae_in,lp->graph->ae_out,esize);i=1;
  80.                     }
  81.                 }
  82.                 lp=lp->next;
  83.             }
  84.             /*  out(b)=gen(B) U (in(B)-kill(B)  */
  85.             memcpy(tmp,g->ae_in,esize);
  86.             bvdiff(tmp,g->ae_kill,esize);
  87.             bvunite(tmp,g->ae_gen,esize);
  88.             if(!bvcmp(tmp,g->ae_out,esize)){changed=1;memcpy(g->ae_out,tmp,esize);}
  89.             g=g->normalout;
  90.         }
  91.     }while(changed);
  92.     if(DEBUG&1024) printf("\n");
  93.     free(tmp);
  94. }
  95.  
  96.  
  97. int compare_objs(struct obj *o1,struct obj *o2,int t)
  98. /*  Vergleicht die beiden Objekte; liefert 0, wenn sie gleich sind, sonst   */
  99. /*  1 oder -1, um eine Ordnung darauf zu definieren                         */
  100. {
  101.     int i1,i2;
  102.     i1=o1->flags;i2=o2->flags;
  103.     if(i1<i2) return(-1);
  104.     if(i1>i2) return(1);
  105.     if(i1&KONST) return(compare_const(&o1->val,&o2->val,t));
  106.     if(i1&VAR){
  107.         i1=o1->v->index; i2=o2->v->index;
  108.         if(i1<i2) return(-1);
  109.         if(i1>i2) return(1);
  110.         i1=zl2l(o1->val.vlong); i2=zl2l(o2->val.vlong);
  111.         if(i1<i2) return(-1);
  112.         if(i1>i2) return(1);
  113.     }
  114.     return(0);
  115. }
  116.  
  117. int compare_exp(const void *a1,const void *a2)
  118. /*  Stub fuer compare_objs, damit als Vergleichsfunktion fuer qsort geht */
  119. {
  120.     struct IC *p1,*p2;int i1,i2;
  121.     p1=*((struct IC **)a1);p2=*((struct IC **)a2);
  122.     if(!p1||!p2) ierror(0);
  123.     i1=p1->code; i2=p2->code;
  124.     if(i1<i2) return(-1);
  125.     if(i1>i2) return(1);
  126.     i1=p1->typf; i2=p2->typf;
  127.     if(i1<i2) return(-1);
  128.     if(i1>i2) return(1);
  129.     i1=compare_objs(&p1->q1,&p2->q1,p1->typf);
  130.     if(i1) return(i1);
  131.     i1=compare_objs(&p1->q2,&p2->q2,p1->typf);
  132.     return(i1);
  133. }
  134. void print_ae(unsigned char *exp)
  135. {
  136.     int i;
  137.     if(!exp){ printf("available expressions not available\n"); return;}
  138.     for(i=0;i<ecount;i++)
  139.         if(BTST(exp,i))
  140.             {printf("%3d,%3d: ",elist[i]->expindex,i);pric2(stdout,elist[i]);}
  141. }
  142. void num_exp(void)
  143. /*  numeriert die Ausdruecke so, dass gleiche Ausdruecke die gleiche    */
  144. /*  nummer erhalten                                                     */
  145. {
  146.     struct IC *p;int c,i;
  147.     if(DEBUG&1024) printf("numerating expressions\n");
  148.     ecount=0;
  149.     if(DEBUG&1024){ printf("num_exp loop1\n");}
  150.     for(p=first_ic;p;p=p->next){
  151.         c=p->code;
  152.         if(p->z.flags&&p->q1.flags&&c!=ASSIGN&&c!=MOVETOREG&&c!=MOVEFROMREG){
  153.             p->expindex=ecount++;
  154.             if(c==ADD||c==MULT||(c>=OR&&c<=AND)){
  155.                 if(p->q2.flags&&compare_objs(&p->q1,&p->q2,p->typf)<0&&(USEQ2ASZ||compare_objs(&p->q1,&p->z,p->typf))){
  156.                     struct obj o;
  157.                     o=p->q1;p->q1=p->q2;p->q2=o;
  158.                 }
  159.             }
  160.         }else p->expindex=-1;
  161.     }
  162.     elist=mymalloc(ecount*sizeof(struct IC *));
  163.     if(DEBUG&1024){ printf("num_exp loop2\n");}
  164.     for(p=first_ic;p;p=p->next){
  165.         if(p->expindex>=0){
  166.             elist[p->expindex]=p;
  167.         }
  168.     }
  169.     esize=(ecount+CHAR_BIT-1)/CHAR_BIT;
  170.     if(DEBUG&1024){ printf("%lu expressions, esize=%lu\nsorting expressions\n",(unsigned long)ecount,(unsigned long)esize);}
  171.     if(ecount>1) qsort(elist,ecount,sizeof(struct IC *),compare_exp);
  172.     if(DEBUG&1024){ printf("renumbering expressions\nnum_exp loop3\n");}
  173.     if(ecount>0){   /*  Aufpassen, da ecount unsigned!  */
  174.         for(c=0;c<ecount-1;c++){
  175.             if(!compare_exp(&elist[c],&elist[c+1]))
  176.                 elist[c+1]->expindex=elist[c]->expindex;
  177.         }
  178.     }
  179.     if(DEBUG&1024) printf("re-sorting expressions\n");
  180.     /*  wieder in die richtige Reihenfolge bringen  */
  181.     for(p=first_ic;p;p=p->next)
  182.         if(p->expindex>=0) elist[p->expindex]=p;
  183.     ae_globals=mymalloc(esize);
  184.     memset(ae_globals,0,esize);
  185.     ae_statics=mymalloc(esize);
  186.     memset(ae_statics,0,esize);
  187.     ae_address=mymalloc(esize);
  188.     memset(ae_address,0,esize);
  189.     ae_drefs=mymalloc(esize);
  190.     memset(ae_drefs,0,esize);
  191.     if(DEBUG&1024){ printf("num_exp loop4\n");}
  192.     ae_kills=mymalloc(vcount*sizeof(unsigned char *));
  193.     for(c=0;c<vcount;c++){
  194.         ae_kills[c]=mymalloc(esize);
  195.         memset(ae_kills[c],0,esize);
  196.     }
  197.     if(DEBUG&1024){ printf("num_exp loop5\n");}
  198.     for(c=0;c<ecount;c++){
  199.         struct Var *v;
  200. /*        if(c<ecount-1&&elist[c]==elist[c+1]) continue;*/  /*  gleiche ueberspringen   */
  201.         p=elist[c];
  202.         if(p->code==ADDRESS) continue;
  203.         if((p->q1.flags&(VAR|VARADR))==VAR){
  204.             v=p->q1.v;
  205.             i=v->index;
  206.             BSET(ae_kills[i],c);
  207.             if(p->q1.flags&DREFOBJ){ BSET(ae_kills[i+vcount-rcount],c);BSET(ae_drefs,c);}
  208.             if(v->nesting==0||v->storage_class==EXTERN) BSET(ae_globals,c);
  209.             if(v->storage_class==STATIC) BSET(ae_statics,c);
  210.             if(v->flags&USEDASADR) BSET(ae_address,c);
  211.         }
  212.         if((p->q2.flags&(VAR|VARADR))==VAR){
  213.             v=p->q2.v;
  214.             i=v->index;
  215.             BSET(ae_kills[i],c);
  216.             if(p->q2.flags&DREFOBJ){ BSET(ae_kills[i+vcount-rcount],c);BSET(ae_drefs,c);}
  217.             if(v->nesting==0||v->storage_class==EXTERN) BSET(ae_globals,c);
  218.             if(v->storage_class==STATIC) BSET(ae_statics,c);
  219.             if(v->flags&USEDASADR) BSET(ae_address,c);
  220.         }
  221.     }
  222. }
  223. void cse_replace(struct flowgraph *g,struct IC *p,struct IC *o,struct Var *v)
  224. /*  ersetzt die cse bei o zu p mit Variable v   */
  225. {
  226.     struct IC *n;
  227.     /*  Kopieranweisung erzeugen    */
  228.     if(DEBUG&1024) printf("cse_replace\n");
  229.     n=mymalloc(ICS);
  230.     n->line=o->line;
  231.     n->file=o->file;
  232.     n->code=ASSIGN;
  233.     n->typf=p->typf;
  234.     n->e